#include <vector>
using namespace std;
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

bool isPalindrome(ListNode *head) {
  vector<int> v;
  while (head != nullptr) {
    v.push_back(head->val);
    head = head->next;
  }
  int left = 0, right = v.size() - 1;
  while (left <= right) {
    if (v[left] == v[right]) {
      left++;
      right--;
    } else {
      return false;
    }
  }
  return true;
}

// 快慢指针解法
bool isPalindrome_(ListNode *head) {
  ListNode *quickPtr = head, *slowPtr = head;
  do {
    // 快指针每次走两步
    if (quickPtr->next != nullptr) {
      quickPtr = quickPtr->next;
    }
    if (quickPtr->next != nullptr) {
      quickPtr = quickPtr->next;
    }
    // 慢指针每次走一步
    if (slowPtr->next != nullptr) {
      slowPtr = slowPtr->next;
    }
  } while (quickPtr->next != nullptr);
  // 退出循环时 快指针指向链表最后一个元素
  // 偶数链表慢指针指向中间左侧位置 奇数链表慢指针指向中间位置
  if (quickPtr == slowPtr) {
    return head->val == quickPtr->val;
  }
  // 反转链表后半部分
  ListNode *rHead = nullptr, *tempA = slowPtr, *tempB = slowPtr;
  while (tempA->next != nullptr) {
    tempB = tempA->next;
    tempA->next = rHead;
    rHead = tempA;
    tempA = tempB;
  }
  tempA->next = rHead;
  // 遍历节点
  bool isOk = true;
  while (head != nullptr && tempB != nullptr) {
    if (head->val != tempB->val) {
      isOk = false;
    }
    head = head->next;
    tempB = tempB->next;
  }
  // 还原链表
  rHead = nullptr;
  while (tempA->next != nullptr) {
    tempB = tempA->next;
    tempA->next = rHead;
    rHead = tempA;
    tempA = tempB;
  }
  tempB->next = rHead;
  return isOk;
}